﻿//添加逗号（模拟）
// https://www.nowcoder.com/practice/f51c317e745649c0900996fd3f683aed?tpId=290&tqId=39934&ru=/exam/oj
//#include <iostream>
//
//using namespace std;
//
//int main()
//{
//	string s;
//	cin >> s;
//	string ret;
//
//	int n = s.size();
//	for (int i = 0; i < n; i++)
//	{
//		ret += s[i];
//		if ((n - 1 - i) % 3 == 0 && i != n - 1)
//		{
//			ret += ',';
//		}
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}

//跳台阶（动态规划）
// https://www.nowcoder.com/practice/bfb2a2b3cdbd4bd6bba0d4dca69aa3f0?tpId=230&tqId=39749&ru=/exam/oj
//#include <iostream>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int a = 1, b = 1, c;
//	for (int i = 2; i <= n; i++)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//	}
//	if (n == 0 || n == 1) cout << n << endl;
//	else cout << c << endl;
//	return 0;
//}

//扑克牌顺⼦（排序）
// https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&ru=/exam/oj
//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;

//未完成
//class Solution 
//{
//public:
//
//    bool IsContinuous(vector<int>& n) 
//    {
//        sort(n.begin(), n.end());
//        int i = 0;
//        int flag = 1;
//        for (i; i < n.size()- 2; i++)
//        {
//            if (n[i] + 1 != n[i + 1] && n[i] != 0 && n[i + 1] != 0 && n[i + 2] != n[i] + 2)
//            {             
//                return false;
//            }
//        }
//        
//
//            return true;
//        
//    }
//};


//class Solution
//{
//    bool hash[14] = { 0 };
//public:
//    bool IsContinuous(vector<int>& numbers)
//    {
//        int maxV = -1;
//        int minV = 20;
//
//        for (auto& e : numbers)
//        {
//            if (e)
//            {
//                if (hash[e]) return false;
//                hash[e] = true;
//                maxV = max(maxV, e);
//                minV = min(minV, e);
//            }
//        }
//
//        return (maxV - minV) <= 4;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> v = { 0,3,2,6,4 };
//    cout <<  s.IsContinuous(v) << endl;
//
//    return 0;
//}

//辗转相除法求最大公倍数
//#include <iostream>
//using namespace std;
//
//int main()
//{
//    int a, b;
//    cin >> a >> b;
//
//    int x = 0;
//    if (a < b)
//    {
//        x = b;
//        b = a;
//        a = x;
//    }
//
//    int m = a % b;
//    int n = a * b;
//    while (m)
//    {
//        a = b;
//        b = m;
//        m = a % b;
//    }
//
//    cout << n / b << endl;
//
//    return 0;
//}


// 最⻓回⽂⼦串（回⽂串）
// https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=182&tqId=34752&ru=/exam/oj
//#include <iostream>
//using namespace std;
//class Solution
//{
//public:
//    int getLongestPalindrome(string A)
//    {
//        int ret = 1;
//        int n = A.size();
//        for (int i = 1; i < n; i++)
//        {
//            int left = i - 1;
//            int right = i + 1;
//            while (left >= 0 && right < n && A[left] == A[right])
//            {
//                left--;
//                right++;
//            }
//            ret = max(ret, right - left - 1);
//
//            left = i - 1;
//            right = i;
//            while (left >= 0 && right < n && A[left] == A[right])
//            {
//                left--;
//                right++;
//            }
//            ret = max(ret, right - left - 1);
//        }
//
//        return ret;
//    }
//};


//class Solution
//{
//public:
//    int getLongestPalindrome(string s)
//    {
//        int ret = 1, n = s.size();
//        for (int i = 1; i < n; i++)
//        {
//            // 当⻓度是奇数的时候
//            int left = i - 1, right = i + 1;
//            while (left >= 0 && right < n && s[left] == s[right])
//            {
//                left--;
//                right++;
//            }
//            ret = max(ret, right - left - 1);
//            // 当⻓度是偶数的时候
//            left = i - 1, right = i;
//
//                while (left >= 0 && right < n && s[left] == s[right])
//                {
//                    left--;
//                    right++;
//                }
//            ret = max(ret, right - left - 1);
//        }
//        return ret;
//    }
//};

//int main()
//{
//    Solution s;
//    string str = "ababc";
//    cout << s.getLongestPalindrome(str) << endl;
//
//
//    return 0;
//}


// 买卖股票的最好时机(⼀)（贪心）
// https://www.nowcoder.com/practice/351b87e53d0d44928f4de9b6217d36bb?tpId=230&tqId=39767&ru=/exam/oj
//超时
//#include <iostream>
//using namespace std;
//
//const int N = 1e5;
//int p[N];
//
//int main()
//{
//    int n;
//    int ret = 0;
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> p[i];
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = i; j <= n; j++)
//        {
//            if (p[j] > p[i])
//            {
//                ret = max(ret,p[j] - p[i]);
//            }
//        }
//    }
//
//    cout << ret << endl;
//    return 0;
//}
// 
//正确
//#include <iostream>
//using namespace std;
//
//int main()
//{
//    const int N = 1e5;
//    int p[N];
//
//    int n;
//    int ret = 0;
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> p[i];
//    }
//
//    int minV = N;
//    for (int i = 1; i <= n; i++)
//    {
//        minV = min(minV, p[i]);
//        ret = max(ret, p[i] - minV);
//    }
//
//    cout << ret << endl;
//
//    return 0;
//}